   Baraj, ziua 2 (Selectie lot IOI, Cluj, mai 1996)
   Problema 6 (Expresii)

     Fie un num[r prim p. Pe multimea {0,1,...,p-1} se definesc operatiile 
binare +,-,*,/ modulo p n modul urm[tor:
1) a+b modulo p este restul mp[rtirii lui a+b la p; analog pentru *; 
2) Expresia a-b este definit[ ca fiind solutia ecuatiei b+x=a (modulo p); analog 
pentru /;
    Se stie c[ ecuatia b+x=a are ntotdeauna solutie unic[, iar b*x=a are 
solutie unic[ pentru orice bc0; pentru b=0 operatia a/b nu e definit[.
    De exemplu, dac[ p=11 atunci 6+7=2, 6-7=10, 6*7=9, 6/7=4. 
Se stie c[ adunarea si nmulttrea modulo p sunt comutative, asociative, posed[ 
elemente neutre (pe 0, respectiv 1), adunarea este distributiv[ fat[ de nmultire. 
    In plus, pentru orice a exist[ b astfel nct a+b=0; notnd b cu (-a) avem 
c-a=c+(-a)=c+b, pentru orice c.
    De asemenea, pentru orice ac0 exist[ b astfel nct a*b=1; notnd b cu 
(1/a) avem  c/a=c*(1/a)=c*b.
    Dndu-se un num[r prim p, un ntreg d ntre 0 si p-1 si un sir de numere 
cuprinse fiecare ntre 0 si p-1, se cere s[ se introduc[ ntre elementele sirului 
operatorii +,-,*,/ si parantezele corespunz[toare, astfel nct s[ se obtin[ o 
expresie corect[ a c[rei valoare s[ fie d (lucr[nd n aritmetica modulo p).
In caz c[ acest lucru nu este posibil, se va afisa un mesaj corespunz[tor.
Intrarea:
    Numele fisierului de intrare se citeste de la tastatura. Acest fisier contine 
dou[ linii: 
- pe prima linie se g[sesc trei numere ntregi: p,n si d, separate prin spatii 
(2p23, p prim, 1n30, 0dp-1).
- pe urm[toarea linie se g[seste sirul de numere ce formeaz[ expresia (n numere 
ntregi cuprinse ntre 0 si p-1).
Iesirea:
    Numele fisierului de iesire se citeste de la tastatur[. Acest fisier va 
contine o singur[ linie pe care se va g[si expresia generat[ sau mesajul:
Nu exista solutie.
Expresia va fi parantezat[ complet (fiecare operator va avea o pereche de 
paranteze atasate).
Exemple:
1) Intrare:
11 3 6
4 7 9
O iesire corect[:
(4+(7/9))
2) Intrare:
11 3 7
1 1 1
Iesire:
Nu exista solutie.
Not[: Timp maxim de executare pentru fiecare test: 1 minut.
           Punctaj maxim 100 puncte.

=====================================
Program Aritmetica_Mod_P; {SOLUTIA AUTORULUI: RADU LUPSA}
Const
  maxp=100;
  maxn=200;

Type
  elgrup=0..maxp;
  setgrup=set of elgrup;
  lval=array[1..maxn] of setgrup;
  plval=^lval;
Var
  inv:array[elgrup] of integer;
  t:array[1..maxn] of plval;
  v:array[1..maxn] of integer;
  p,n,d:integer;

Function Sum(x,y:integer):integer;
  var s:integer;
  begin
    s:=x+y;
    if s>=p then sum:=s-p else sum:=s;
  end;

Function Dif(x,y:integer):integer;
  begin
    if y=0 then dif:=x else dif:=sum(x,p-y);
  end;

Function Prod(x,y:integer):integer;
  begin
    prod:=x*y mod p;
  end;

Function Rap(x,y:integer):integer;
  begin
    rap:=prod(x,inv[y]);
  end;

Procedure CalcInv;
  var i,j:integer;
  begin
    for i:=1 to p do begin
      j:=1;
      while prod(i,j)<>1 do j:=j+1;
      inv[i]:=j;
    end;
  end;

Procedure InitTab;
  var i:integer;
  begin
    getmem(t[1],n*sizeof(setgrup));
    for i:=1 to n do t[1]^[i]:=[v[i]];
  end;

Procedure Rand(k:integer);
  var i,j1,j2,l:integer;
  begin
    getmem(t[k],(n-k+1)*sizeof(setgrup));
    write(#13,k);
    for i:=1 to n-k+1 do begin
      t[k]^[i]:=[];
      for l:=1 to k-1 do
     for j1:=0 to p-1 do if j1 in t[l]^[i] then
       for j2:=0 to p-1 do if j2 in t[k-l]^[i+l] then begin
         if j2<>0
           then t[k]^[i]:=t[k]^[i]+[sum(j1,j2),dif(j1,j2),
               prod(j1,j2),rap(j1,j2)]
           else t[k]^[i]:=t[k]^[i]+[sum(j1,j2),dif(j1,j2),prod(j1,j2)]
      end;
    end;
  end;

Var nume:string;
  fi,fo:text;
  i,j,k:integer;
Begin
  write('Nume fisier intrare=');
  readln(nume);
  assign(fi,nume);
  reset(fi);
  write('Nume fisier iesire=');
  readln(nume);
  assign(fo,nume);
  rewrite(fo);
  readln(fi,p,n,d);
  CalcInv;
  for i:=1 to n do read(fi,v[i]);
  inittab;
  for i:=2 to n do rand(i);
End.
===================================
    Testele date n baraj:
Test 1:
97 2 23
23 21
==================
Test 2:
11 30 5
4 6 2 8 2 5 2 9 0 1 4 6 2 8 2 5 2 9 0 1 4 6 2 8 2 5 2 9 0 1 4 6 2 8 2 5
2 9 0 1
===================
Test 3:
23 25 5
0 0 0 5 0 0 0 0 5 5 5 9 9 9 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1
======================
Test 4:
11 30 1
1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1
==========================
Test 5:
11 3 6
1 1 1
====================
